package 每日一题;

public class No14最长公共前缀 {

    /**
     * 最优解法: 二分法
     * 最小length的中间数,然后开始一个一个中间值向前进行比较,
     * 中途有不同: right=mid-1;
     * 中途都相同: left+mid+1;
     */
    public static String longestCommonPrefixGood(String[] strs) {

        int minLength=Integer.MAX_VALUE;
        for (int i = 0; i < strs.length; i++) {
            minLength=Math.min(minLength,strs[i].length());
        }
        if(minLength==0){
            return "";//没有公共前缀
        }

        int left=0;
        int right=minLength-1;
        int mid=0;

        while (left<=right){
            mid=(right-left)/2+left;
            boolean flag = isOneCharEquals(strs, mid);
            if(flag){
                left=mid+1;
            }else{
                right=mid-1;
            }

        }

        return strs[0].substring(0,left);

    }

    private static boolean isOneCharEquals(String[] strs,int index) {
        //一个个的向前比较
        for (int i = index; i >= 0; i--) {
            char c=strs[0].charAt(i);
            for (int j = 1; j < strs.length; j++) {
                if(c!=strs[j].charAt(i)){
                    return false;
                }
            }
        }
        return true;
    }



    /**
     * 3(2)最长公共前缀
     */
    public static String longestCommonPrefix(String[] strs) {

        //如果数组为空或者数组长度为0直接返回""表示没有公共前缀
        if(strs==null||strs.length==0)
            return "";

        String maxPrefix=strs[0];//初始化最长前缀为第一个字符串

        /**
         * 一个for就可以解决此问题
         */
        for (int i = 1; i < strs.length; i++) {
            //因为取了第一个字符串,那么就开始和第二个及其以后的字符串开始一一比较

            maxPrefix = compareString(maxPrefix, strs[i]);//得到两个字符串的公共前缀
            if(maxPrefix.equals("")){
                //这表明两个字符串没有公共前缀,既然这两个字符串没有公共前缀,那么所有字符串就没有公共前缀,没有比较下去的必要了
                break;
            }
        }
        return maxPrefix;
    }

    /**
     * 此方法返回的是当前两个字符串的最长前缀
     */
    private static String compareString(String str1,String str2){

        //取两个字符串最短的长度
        int length=Math.min(str1.length(),str2.length());
        String result="";//先定义好本次要返回的结果

        //遍历两个字符串
        for(int i=0;i<length;i++){
            //每次豆截取字符串的第i个字符
            char c1=str1.charAt(i);
            char c2=str2.charAt(i);

            if(c1==c2){
                //如果两个字符相等,那么他们就有公共前缀
                result=result+c1;//这里加上c1或者c2都可以因为它们两个是相等的
            }else{
                //直接break出去,因为当前两字符已经不相等了,最长公共前缀已经出现
                break;
            }
        }
        return result;//返回结果
    }



    public static void main(String[] args) {
        String[] arr={"abasb","ababss","absqw"};
        String s1 = longestCommonPrefix(arr);
        System.out.println(s1);
        String s2= longestCommonPrefixGood(arr);
        System.out.println(s2);
    }

}
